package com.c2b.algorithm.leetcode.base.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/generate-parentheses/description/">括号生成(Generate Parentheses)</a>
 * <p>数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 3
 *      输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * 示例 2：
 *      输入：n = 1
 *      输出：["()"]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>  1 <= n <= 8</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/25 18:25
 */
public class LC0022GenerateParentheses_M {

    static class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> retList = new ArrayList<>();
            dfs(n, n, "", retList);
            return retList;
        }

        private void dfs(int leftParenthesesNumber, int rightParenthesesNumber, String currStr, List<String> ret) {
            // 左、右括号都不剩余了，递归终止
            if (leftParenthesesNumber == 0 && rightParenthesesNumber == 0) {
                ret.add(currStr);
                return;
            }
            // 如果左括号还剩余的话，可以拼接左括号
            if (leftParenthesesNumber != 0) {
                dfs(leftParenthesesNumber - 1, rightParenthesesNumber, currStr + "(", ret);
            }
            // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
            if (rightParenthesesNumber > leftParenthesesNumber) {
                dfs(leftParenthesesNumber, rightParenthesesNumber - 1, currStr + ")", ret);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (String parenthesis : solution.generateParenthesis(1)) {
            System.out.println(parenthesis);
        }
    }
}
